package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.List;

public class problems22 {
    private int n;
    private int open = 0;
    private List<String> res = new ArrayList<String>();
    private StringBuilder path = new StringBuilder();

    public List<String> generateParenthesis(int _n) {
        n = _n * 2;
        dfs(0, 0);
        return res;
    }

    private void dfs(int i, int open) {
        if (i == n) {
            res.add(path.toString());
            return;
        }

        //左
        if (open < n / 2) {
            path.append('(');
            dfs(i + 1, open + 1);
            path.deleteCharAt(path.length() - 1);
        }

        //右
        if (i - open < open) {
            path.append(')');
            dfs(i + 1, open);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
